﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Diagnostics;

namespace TSP
{
    class PermutationGenerator
    {
        private int _n;                
        public int N
        {
          get { return _n; }
          set { _n = value; }
        }
        private int[] v;
        private int[] minV;      
        private float _minFitness = float.MaxValue;
        private float temp;
        public float MinFitness
        {
            get { return _minFitness; }
            set { _minFitness = value; }
        }
        public int[] MinV
        {
            get { return minV; }
            set { minV = value; }
        }
        //StreamWriter wr = new StreamWriter(@"permutationTemp.tour");


        public delegate float CaculateDistance(int city1, int city2);
        public CaculateDistance calDistance;
        public delegate void WriteResulToFile(string fileName, int[] chr, float fitness, Stopwatch time);
        public WriteResulToFile writeResult;

        public PermutationGenerator(int num)
        {
            _n=num;
        }
        public void init()
        {            
            v = new int[_n];
            minV = new int[_n];
            for (int i=0; i<_n; i++)
            {
                v[i]=i+1;//initialise
            }
        }
        public void go()
        {
            
            Permute(v, 0, _n);
            //writeResult(@"permutation.tour", minV, _minFitness);
            //wr.Close();
        }
        /*==================================
          Function  Permute
          ==================================*/
        void Permute(int[] v, int start, int n)
        {
            //Print(v,n);
            temp = calculateFitness();
            if (temp < _minFitness)
            {
                _minFitness = temp;
                Array.Copy(v, minV, InOutData.NumOfCity);
                //Print(minV, InOutData.numOfCity);
            }
            #region Debug
            //if (start == n - 1)
            //{
            //    temp = calculateFitness();
            //    if (temp < _minFitness)
            //    {
            //        _minFitness = temp;
            //        Array.Copy(v, minV, InOutData.numOfCity);
            //        Print(minV, InOutData.numOfCity);
            //    }                
            //    //Print(v, InOutData.numOfCity);
            //}


            //for (int i = 0; i < InOutData.numOfCity; i++)
            //{
            //    wr.Write(v[i] + " ");
            //}
            //wr.WriteLine();
            //wr.WriteLine(temp);
            //wr.WriteLine();
            #endregion                      
            if (start < n)
            {                
                for(int i=n-2; i>=start; i--)
                {
                    for(int j=i+1; j<n; j++)
                    {
                        Swap(ref v,i,j);
                        Permute(v,i+1,n);
                    }
                    Rotate_Left(ref v,i,n);
                }
            }
        }
 
        /*==============================
          Function Print
          =============================*/
        void Print(int[] v,int size)
        {
            for (int i = 0; i < size; i++)
            {
                Console.Write(v[i] + " ");
            }
            Console.WriteLine();
        }

        public float calculateFitness()
        {
            float s = 0;
            for (int i = 0; i < InOutData.NumOfCity - 1; i++)
            {
                s = s + this.calDistance(v[i] - 1, v[i + 1] - 1);
            }
            s = s + this.calDistance(v[InOutData.NumOfCity-1]-1,v[0]-1);
            return s;
        }

        /*==============================
          Function swap
          ==============================*/
        public void Swap(ref int[] v,int i,int j)
        {
            int t;
            t = v[i];
            v[i] = v[j];
            v[j] = t;
        }
 
        /*===========================
          Function rotate left
          ===========================*/
        public void Rotate_Left(ref int[] v,int go,int n)
        {
            int tmp = v[go];
            for (int i=go; i<n-1; i++)
            {
                v[i] = v[i+1];
            }
            v[n-1] = tmp;
        }
    }
}
